package beusoft.ccjk.com.calculator.huffman;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.concurrent.BlockingDeque;

import javax.swing.LookAndFeel;

/**
 * Created by CCJK on 2018/12/13.
 */

public class Huffman {

    /**
     * 对应一个字符出现的次数
     */
    static class Node {
        char mChar;
        int count;
        String code;
        Node left;
        Node right;

        public Node(int count) {
            this.count = count;
        }

        public Node(char aChar, int count) {
            mChar = aChar;
            this.count = count;
        }
    }


    public static void main(String... args) {
        Huffman huffman = new Huffman();
        String s = "@abcdefghijklmnfghijklmnfghijklmnopqrstuvwxyzeenopqrstuvwxyzeenopqrstuvwxyzeeeeeeeeeeeaabblakgi    mahzpod";
        String temp = "爱 你 my favorite food is apple 我";
        List<Node> nodes = huffman.getNodes(s);
        PriorityQueue<Node> queue = huffman.getPriorityQueue(nodes);
        Node tree = huffman.getHuffmanTree(queue);
        try {
            String encodedString = huffman.encode(tree, temp);
            String decodedString = huffman.decode(tree, encodedString);
            println("encodedString: " + encodedString);
            println("decodedString: " + decodedString);
            if (decodedString.contains("@")) {
                println("编码的数据中包含不能识别的字符");
            } else if (temp.equals(decodedString)) {
                println("算法正确");
            } else {
                println("算法错误");

            }
        } catch (Exception e) {
            e.printStackTrace();

        }


    }

    /**
     * 1
     * 根据文本获取每个字符对应出现的次数
     *
     * @param s
     * @return
     */
    private List<Node> getNodes(String s) {
        if (s == null || s.length() == 0) return null;
        Map<String, Integer> map = new HashMap<>();
        int len = s.length();
        String temp;
        for (int i = 0; i < len; i++) {
            temp = s.charAt(i) + "";
            Integer value = map.get(temp);
            if (value == null) {
                map.put(temp, 1);
            } else {
                map.put(temp, value + 1);
            }

        }
        List<Node> list = new ArrayList<>();
        for (String s1 : map.keySet()) {
            char ch = s1.charAt(0);
            list.add(new Node(ch, map.get(s1)));
        }
        return list;
    }

    /**
     * 2
     * 将集合转换为优先级队列
     *
     * @param nodes
     * @return
     */
    private PriorityQueue<Node> getPriorityQueue(List<Node> nodes) {
        PriorityQueue<Node> queue = new PriorityQueue<>(nodes.size() + 10, new Comparator<Node>() {
            @Override
            public int compare(Node t1, Node t2) {
                return t1.count - t2.count;
            }
        });
        queue.addAll(nodes);
        return queue;
    }

    /**
     * 3
     * 根据优先级队列建立哈夫曼树
     *
     * @param queue
     * @return
     */
    private Node getHuffmanTree(PriorityQueue<Node> queue) {
        Node parent = null;
        Node node1;
        Node node2;
        while (queue.size() > 1) {
            node1 = queue.poll();
            node2 = queue.poll();
            parent = new Node(node1.count + node2.count);
            parent.left = node1;
            parent.right = node2;
            queue.add(parent);
        }
        Node tree = queue.poll();
        tree.code = "";
        addCodeToTree(tree);
        return tree;
    }

    /**
     * 将给哈夫曼树的叶节点 加上编码
     *
     * @param tree
     */
    private void addCodeToTree(Node tree) {
        if (tree == null) return;
        if (tree.left != null) {
            tree.left.code = tree.code + "0";
            addCodeToTree(tree.left);
        }
        if (tree.right != null) {
            tree.right.code = tree.code + "1";
            addCodeToTree(tree.right);
        }

    }


    /**
     * 4
     * 同过哈夫曼树将字符串编码
     *
     * @param huffmanTree
     * @param s
     * @return
     */
    private String encode(Node huffmanTree, String s) throws Exception {
        StringBuilder stringBuffer = new StringBuilder();
        int len = s.length();
        Node temp;
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            temp = find(huffmanTree, ch);
            if (temp != null) {
                stringBuffer.append(temp.code);
            } else {
                //该字符在哈夫曼树中没有对应的编码,添加用默认字符的代替
                temp = find(huffmanTree, '@');
                stringBuffer.append(temp.code);
            }
        }
        return stringBuffer.toString();
    }

    private Node find(Node tree, char ch) {
        if (tree.mChar == ch) {
            return tree;
        }
        Node left = null, right = null;
        if (tree.left != null) {
            left = find(tree.left, ch);
        }
        if (tree.right != null) {
            right = find(tree.right, ch);
        }

        if (left != null) {
            if (left.mChar == ch)
                return left;
        } else if (right != null) {
            if (right.mChar == ch)
                return right;
        }

        return null;
    }

    /**
     * 5
     * 通过哈夫曼树解码编码后的数据
     *
     * @param huffmanTree
     * @param s
     * @return
     */
    private String decode(Node huffmanTree, String s) {
        StringBuilder stringBuffer = new StringBuilder();
        int len = s.length();
        Node tree = huffmanTree;
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (ch == '0') {
                tree = tree.left;
            } else if (ch == '1') {
                tree = tree.right;
            } else {
                throw new RuntimeException("错误的编码");
            }
            if (tree.left == null && tree.right == null) {
                stringBuffer.append(tree.mChar);
                tree = huffmanTree;
            }
        }
        return stringBuffer.toString();
    }

    private static void println(Object o) {
        System.out.println(o);
    }

    private static void print(Object o) {
        System.out.print(" " + o);
    }

    private static void printArr(int arr[]) {
        print("[");
        for (int i = 0; i < arr.length; i++) {
            if (i == arr.length - 1) {
                print(arr[i]);
            } else {
                print(arr[i] + " , ");
            }

        }
        print("]");
    }
}
